package com.剑指offer;

import java.util.ArrayList;
import java.util.List;

public class 二叉树的遍历
{
    private static TreeNode root;
    private static List<TreeNode> list = new ArrayList<TreeNode>();

    public static void init()
    {
//        TreeNode x = new TreeNode("x", null, null);
//        TreeNode y = new TreeNode("y", null, null);
//        TreeNode d = new TreeNode("d", x, y);
//        TreeNode e = new TreeNode("e", null, null);
//        TreeNode f = new TreeNode("f", null, null);
//        TreeNode c = new TreeNode("c", e, f);
//        TreeNode b = new TreeNode("b", d, null);
//        TreeNode a = new TreeNode("a", b, c);
//        root = a;
    }

    public static void preOrder(TreeNode root)
    {
        list.add(root);
        if (root.left != null)
        {
            preOrder(root.left);
        }
        if (root.right != null)
        {
            preOrder(root.right);
        }
    }

    public static void inOrder(TreeNode root)
    {
        if (root.left != null)
        {
            inOrder(root.left);
        }
        list.add(root);
        if (root.right != null)
        {
            inOrder(root.right);
        }
    }

    public static void postOrder(TreeNode root)
    {
        if (root.left != null)
        {
            postOrder(root.left);
        }
        if (root.right != null)
        {
            postOrder(root.right);
        }
        list.add(root);
    }

    public static void main(String[] args)
    {
        init();
        System.out.println("先序遍历");
        preOrder(root);
        for (TreeNode node : list)
        {
            System.out.print(node.val + " ");
        }
        System.out.println();
        list.clear();

        System.out.println("中序遍历");
        init();
        inOrder(root);
        for (TreeNode node : list)
        {
            System.out.print(node.val + " ");
        }
        System.out.println();
        list.clear();

        System.out.println("后序遍历");
        init();
        postOrder(root);
        for (TreeNode node : list)
        {
            System.out.print(node.val + " ");
        }
    }

}



